#! /usr/bin/env python
# -*- coding: utf-8 -*-

# Copyright (c) Huoty, All rights reserved
# Author: Huoty <sudohuoty@163.com>
# CreateTime: 2020-04-14 20:16:46

import timeit
import random


def gen_random_data(length=10, mix=0, max=100):
    return [random.randint(mix, max) for _ in range(length)]


def bubble_sort(array):
    arr_len = len(array)
    for i in range(0, arr_len - 1):
        for j in range(0, arr_len - i - 1):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]
    return array


def select_sort(array):
    arr_len = len(array)
    for i in range(0, arr_len - 1):
        mix_index = i
        for j in range(i + 1, arr_len):
            if array[mix_index] > array[j]:
                mix_index = j
        if mix_index != i:  # 优点是每次循环最多只需交换一次数次
            array[i], array[mix_index] = array[mix_index], array[i]
    return array


def insert_sort(array):
    arr_len = len(array)
    # 定义第 i 个元素之前是排好序的数据，之后为待排序的数据
    for i in range(1, arr_len):
        uptake = array[i]  # 表示抽取出来要插入的数据
        j = i
        # 从第 i 个元素开始向前比较，如果小于前一个元素则前边的元素后移，如果大于前一个元素则无需在比较了
        while j > 0 and uptake < array[j - 1]:
            array[j] = array[j - 1]
            j -= 1
        if j != i:
            array[j] = uptake  # 把抽出来的牌放到空位上
    return array


def shell_sort(array):
    arr_len = len(array)
    if arr_len <= 1:
        return array

    def shell_insert(array, gap):
        arr_len = len(array)
        for i in range(gap, arr_len):
            uptake = array[i]  # 记录要插入的元素
            j = i - gap  # 跨 gap 的步长进行插入排序
            while j >= 0 and uptake < array[j]:
                array[j + gap] = array[j]
                j -= gap
            if j != i - gap:
                array[j + gap] = uptake
        return array

    gap = arr_len // 2  # 初步增量，即先将数组分成 gap 组进行插入排序
    while gap >= 1:
        shell_insert(array, gap)
        gap = gap // 2
    return array


def quick_sort(array, start=0, end=None):
    if end is None:
        end = len(array) - 1

    # 递归的退出条件
    if start >= end:
        return

    pivot = start       # 选取起始元素为要寻找位置的基准元素
    pivot_value = array[pivot]
    left = start        # 序列左边的由左向右移动的游标
    right = end         # 序列右边的由右向左移动的游标
    while left < right:
        # 如果列表后边的元素不比基准元素小，则游标往左移动
        while left < right and array[right] >= pivot_value:
            right -= 1
        # 如果列表前边的元素不比基准元素大，则游标向右移动
        while left < right and array[left] <= pivot_value:
            left += 1
        if left < right:
            # 此时已在左边找到一个比基准大的元素，在右边找到一个比基准小的元素
            # 将这两个元素交换位置，以保证后续左边的元素都比基准小，右边的元素都比基准大
            array[left], array[right] = array[right], array[left]

    # 由于左右两边游标不断向彼此逼近，此时 left 与 right 重合，该位置为基准放置的合适位置
    # 将重合位置的元素与基准元素交换，致此便完成了一次分组
    array[pivot], array[left] = array[left], array[pivot]

    # 继续对基准元素左边的子序列进行快速排序
    quick_sort(array, start, left-1)
    # 继续对基准元素右边的子序列进行快速排序
    quick_sort(array, left+1, end)
    return array


def merge_sort(array):
    arr_len = len(array)
    if arr_len <= 1:
        return array

    def merge(left, right):
        left_len = len(left)
        right_len = len(right)
        i = j = 0  # 用 i，j 分别表示左右两个列表的游标
        result = []
        while i < left_len and j < right_len:
            if left[i] <= right[j]:
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1

        result = result + left[i:] + right[j:]
        return result

    mid = arr_len // 2
    left = merge_sort(array[0:mid])
    right = merge_sort(array[mid:arr_len])
    sorted_array = merge(left, right)
    array[:] = sorted_array[:]
    return array


def heap_sort(array):
    arr_len = len(array)

    def shift_down(end, index):
        lchild = 2 * index + 1
        cur_pos = index
        while lchild <= end:
            max_child = lchild
            rchild = lchild + 1
            if rchild <= end and array[lchild] < array[rchild]:
                max_child = rchild
            if array[cur_pos] >= array[max_child]:
                break
            array[cur_pos], array[max_child] = array[max_child], array[cur_pos]
            cur_pos = max_child
            lchild = 2 * cur_pos + 1

    def heapify():
        mid_index = (arr_len - 1) // 2
        for index in range(mid_index, -1, -1):
            shift_down(arr_len - 1, index)

    heapify()  # 先构建一个大顶堆
    for index in range(arr_len - 1, 0, -1):
        array[0], array[index] = array[index], array[0]
        shift_down(index - 1, 0)

    return array


def test_sort_func(func, array):
    print("Testing %s :" % func.__name__)
    take_time = timeit.timeit(stmt=lambda: func(array), number=1)
    print("Sort Result: ", array)
    print("Take: %s seconds" % take_time)


if __name__ == "__main__":
    arr = gen_random_data(50)
    print("Raw Array: ", arr)
    # test_sort_func(bubble_sort, arr.copy())
    # test_sort_func(select_sort, arr.copy())
    # test_sort_func(insert_sort, arr.copy())
    # test_sort_func(shell_sort, arr.copy())
    test_sort_func(quick_sort, arr.copy())
    # test_sort_func(merge_sort, arr.copy())
    # test_sort_func(heap_sort, arr.copy())
